#include <bits/stdc++.h>

using namespace std;


// 另一棵树的子树
// 给你两棵二叉树root和subRoot
// 检验root中是否包含和subRoot具有相同结构和节点值的子树
// 如果存在，返回true
// 否则，返回false
// 测试链接 : https://leetcode.cn/problems/subtree-of-another-tree/

// 不要提交这个类
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution 
{
public:
	// 方法1
	// 暴力递归
	// 时间复杂度O(n * m)
    bool isSubtree(TreeNode* t1, TreeNode* t2) 
    {
        if(t1 != nullptr && t2 != nullptr)
        {
            return same(t1, t2) || isSubtree(t1->left, t2) || isSubtree(t1->right, t2);
        }
        return t2 == nullptr;
    }

    // 判断a和b这两棵树是否完全一样
    bool same(TreeNode* a, TreeNode* b)
    {
        if(a == nullptr && b == nullptr) return true;
        if(a != nullptr && b != nullptr)
            return a->val == b->val && same(a->left, b->left) && same(a->right, b->right);
        return false;
    }

	// 方法2
	// 二叉树先序序列化 + KMP算法匹配
	// 时间复杂度O(n + m)
    bool isSubtree2(TreeNode* t1, TreeNode* t2) 
    {
        if(t1 != nullptr && t2 != nullptr)
        {
            vector<string> s1, s2;
			serial(t1, s1);
			serial(t2, s2);
			return kmp(s1, s2) != -1;
        }
        return t2 == nullptr;
    }

    void serial(TreeNode* root, vector<string>& path)
    {
        if(root == nullptr)
            path.emplace_back("null");
        else
        {
            path.emplace_back(to_string(root->val));
            serial(root->left, path);
            serial(root->right, path);
        }
    }

    int kmp(vector<string>& s1, vector<string>& s2)
    {
        int n = s1.size(), m = s2.size(), x = 0, y = 0;
        vector<int> next = nextArray(s2, m);
        while(x < n && y < m)
        {
            if(s1[x] == s2[y])
                ++x, ++y;
            else if(y == 0)
                ++x;
            else
                y = next[y];
        }
        return y == m ? x - y : -1;
    }

    vector<int> nextArray(vector<string>& s, int m)
    {
        if(m == 1) return {-1};
        vector<int> next(m);
        next[0] = -1, next[1] = 0;
        int i = 2, cn = 0;
        while(i < m)
        {
            if(s[i - 1] == s[cn])
                next[i++] = ++cn;
            else if(cn > 0)
                cn = next[cn];
            else
                next[i++] = 0;
        }
        return next;
    }
};